package 回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
给定一个无重复元素的数组 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取.

说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

 */
public class 组合总和 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	 List<List<Integer>> res=new ArrayList<List<Integer>>();
    	 //排序
         Arrays.sort(candidates);
         backtrack(candidates, target, res, 0, new ArrayList<Integer>());
         return res;
    }

	private void backtrack(int[] candidates, int target, List<List<Integer>> res, int i, ArrayList<Integer> tempList) {
		if (target<0) {
			return;
		}
		if (target==0) {
			res.add(new ArrayList<>(tempList));
            return;
		}
		 for (int start = i; start < candidates.length; start++) {
			 if (target < 0) break;
			 tempList.add(candidates[start]);
			 backtrack(candidates, target - candidates[start], res, start, tempList);
			 tempList.remove(tempList.size() - 1);
		 }
	}
}
